home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1993 July / InfoMagic USENET CD-ROM July 1993.ISO / sources / unix / volume3 / hdiff < prev    next >
Encoding:
Internet Message Format  |  1986-11-30  |  47.2 KB
  1. From: Dennis Bednar <talcott!seismo!rlgvax!dennis>
  2. Subject: hdiff: - source file compare program
  3. Newsgroups: mod.sources
  4. Approved: jpn@panda.UUCP
  5.  
  6. Mod.sources:  Volume 3, Issue 117
  7. Submitted by: Dennis Bednar <talcott!seismo!rlgvax!dennis>
  8.  
  9. #! /bin/sh
  10. # This is a shell archive, meaning:
  11. # 1. Remove everything above the #! /bin/sh line.
  12. # 2. Save the resulting text in a file.
  13. # 3. Execute the file with /bin/sh (not csh) to create the files:
  14. #    hdiff.hlp
  15. #    Makefile
  16. #    hdiff.c
  17. #    remwhite.c
  18. #    stripnl.c
  19. #    stripnl.h
  20. # This archive created: Sat Feb  8 07:42:17 1986
  21. export PATH; PATH=/bin:$PATH
  22. echo shar: extracting "'hdiff.hlp'" '(2433 characters)'
  23. if test -f 'hdiff.hlp'
  24. then
  25.     echo shar: will not over-write existing file "'hdiff.hlp'"
  26. else
  27. cat << \SHAR_EOF > 'hdiff.hlp'
  28. hdiff [-cdmvw] oldfile newfile
  29.  
  30. Source file compare program.
  31. Yet another source compare program like diff.  This one reports moved lines,
  32. not delete/insert as the UNIX diff does.  The h is in honor of Paul Heckel,
  33. the guy who first wrote about this algorithm in CACM July 1978.
  34.  
  35. One of c,d, or m should be used to adjust the internal algorithm.
  36. Currently I am playing with the algorithm.
  37.  
  38. Switches
  39.     -c = use a "count between the start of the other move block and
  40.         the first line in the other file which matched this move
  41.         block" to determine moved blocks [DEFAULT]
  42.     -d = use a "drop" or relative slope to determine moved blocks
  43.     -m = use "mononotonically increasing by one" to determine moved blocks
  44.     -v = verbose (debugging)
  45.     -w = compress white space only on each line before comparison,
  46.         and remove leading white space (remwhite -a option).
  47.  
  48. (see CACM, April 78, "A Technique for Isolating Differences Between Files",
  49. by Paul Heckel).
  50.  
  51. Output:
  52.     The output is identical in meaning to the output from UNIX diff,
  53.     except that a "move" command is present here, but not in diff.
  54.  
  55. DELETES
  56. -------
  57. old d new         // Single line delete - Old line number 'old' is
  58.             // deleted after new line numbered 'new'
  59. startold,endold d new    // Block line delete - Old block of lines 'startold'
  60.             // to 'endold' are deleted after new line number 'new'
  61.  
  62. INSERTS
  63. -------
  64. old a new        // After old line number 'old' is new line number 'new'
  65. old a startnew,endnew    // After old line number 'old', new lines numbered
  66.             // 'startnew' to 'endnew'
  67.  
  68. CHANGES
  69. -------
  70. old c new        // Change one line to one new line.  The old line
  71.             // numbered 'old' becomes new line numbered 'new'
  72. old c startnew,endnew    // Change one line to a block of lines.  Old line
  73.             // numbered 'old' becomes the new set of lines.
  74. startold,endold c new    //  Change a block of old lines to one new line.
  75. startold,endold c startnew,endnew    // Change a block of lines to
  76.             // a different block of lines.
  77.  
  78. MOVES
  79. -----
  80. old m new        // Old line number 'old' is moved to new line
  81.             // number 'new'
  82. startold,endold m startnew,endnew  // The old block of lines have been moved
  83.             // and the old line numbers have changed.
  84.  
  85.  
  86. For DELETES, INSERTS, and CHANGES (but not MOVES) the old line and new lines
  87. are displayed as follows (same as the UNIX diff):
  88. < old line
  89. > new line
  90.  
  91. BUGS:
  92.     Hdiff is limited to files with at most 5000 lines per file.
  93.     To fix, recompile hdiff.c with a larger MAXLINES #define.
  94. SHAR_EOF
  95. if test 2433 -ne "`wc -c < 'hdiff.hlp'`"
  96. then
  97.     echo shar: error transmitting "'hdiff.hlp'" '(should have been 2433 characters)'
  98. fi
  99. fi
  100. echo shar: extracting "'Makefile'" '(1034 characters)'
  101. if test -f 'Makefile'
  102. then
  103.     echo shar: will not over-write existing file "'Makefile'"
  104. else
  105. cat << \SHAR_EOF > 'Makefile'
  106. SRC = hdiff.c remwhite.c stripnl.c stripnl.h hdiff.mk
  107. # also the hdiff help file is source but it is renamed on the copy
  108.  
  109. # change this for your site
  110. INSTALLDIR = .
  111.  
  112.  
  113. hdiff: hdiff.o remwhite.o stripnl.o
  114.     cc -O hdiff.o remwhite.o stripnl.o
  115.     mv a.out hdiff
  116.  
  117. hdiff.o: stripnl.h
  118.     cc -O -c hdiff.c
  119.  
  120. remwhite.o: stripnl.h
  121.     cc -O -USTAND -c remwhite.c
  122.  
  123. stripnl.o: stripnl.h
  124.     cc -O -c stripnl.c
  125.  
  126. clean:
  127.     rm -f hdiff.o remwhite.o stripnl.o hdiff
  128.  
  129. install: hdiff
  130.     cp hdiff $(INSTALLDIR)
  131.  
  132. # distribute hdiff. personal for dennis only.
  133. dist:
  134.     rm -rf /tmp/dpb
  135.     mkdir /tmp/dpb
  136.     cp $(SRC) /tmp/dpb
  137.     cp ../help/hdiff /tmp/dpb/hdiff.hlp    # help file
  138.     (cd /tmp/dpb; make -f hdiff.mk makeshar)
  139.  
  140. makeshar:
  141.     splitfiles *      # split source files into little bundles
  142.     for i in list.* ; \
  143.     do \
  144.         makeshar `cat $$i` > shar.$$i ; \
  145.     done
  146.  
  147.  
  148. # you must run make -f hdiff.mk makeshar first
  149. # sends shar files to mod.sources
  150. # hardcoded for 2 bundles
  151. sendtonet:
  152.     for i in 1 2 ; \
  153.     do \
  154.         Mail < shar.list.$$i -s "hdiff: - part $$i of 2" sources@panda.uucp; \
  155.     done
  156. SHAR_EOF
  157. if test 1034 -ne "`wc -c < 'Makefile'`"
  158. then
  159.     echo shar: error transmitting "'Makefile'" '(should have been 1034 characters)'
  160. fi
  161. fi
  162. echo shar: extracting "'hdiff.c'" '(34748 characters)'
  163. if test -f 'hdiff.c'
  164. then
  165.     echo shar: will not over-write existing file "'hdiff.c'"
  166. else
  167. cat << \SHAR_EOF > 'hdiff.c'
  168. /*
  169.  * f=hdiff.c  (In honor of Mr Heckel, the guy who thought up this
  170.  * algorithm).
  171.  *
  172.  * author - dennis bednar  8 22 84
  173.  * Source file comparison program similar to UNIX diff, except this
  174.  * version outputs moved blocks whereas UNIX diff reports it as
  175.  * delete/add blocks.
  176.  *
  177.  * Algorithm from "A Technique for Isolating Differences Between Files"
  178.  * CACM, April 1978, by Paul Heckel.
  179.  * Some ideas for pass 6 were borrowed from "What's The Diff? -- A File
  180.  * Comparator for CP/M", Dr. Dobb's Journal, August 1984, by D.E. Cortesi.
  181.  * The borrowed idea was that when you are at the beginning of two
  182.  * blocks of lines which link with lines in the other file, but don't
  183.  * match, then the smaller ascending block is the "moved block".
  184.  *
  185.  * The pass5a () is coded directly from his his pass5 Pascal procedure.
  186.  * It doesn't work if the old line being looked up in the symbol table
  187.  * isn't unique!!!  You would have to change the format of the linerec
  188.  * record to make it work.  That's why it's commented out.
  189.  *
  190.  * Output
  191.  
  192. DELETES
  193. -------
  194. old d new         // Single line delete - Old line number 'old' is
  195.             // deleted after new line numbered 'new'
  196. startold,endold d new    // Block line delete - Old block of lines 'startold'
  197.             // to 'endold' are deleted after new line number 'new'
  198.  
  199. INSERTS
  200. -------
  201. old a new        // After old line number 'old' is new line number 'new'
  202. old a startnew,endnew    // After old line number 'old', new lines numbered
  203.             // 'startnew' to 'endnew'
  204.  
  205. CHANGES
  206. -------
  207. old c new        // Change old line numbered 'old' to new line numbered
  208.             // 'new'
  209. old c startnew,endnew    // Change one line to a block of lines.  Old line
  210.             // numbered 'old' becomes the new set of lines.
  211. startold,endold c new    //  Change a block of old lines to one new line.
  212. startold,endold c startnew,endnew    // Change a block of lines to
  213.             // a different block of lines.
  214.  
  215. MOVES
  216. -----
  217. old m new        // Old line number 'old' is moved to new line
  218.             // number 'new'
  219. startold,endold m startnew,endnew  // The old block of lines have been moved
  220.             // and the old line numbers have changed.
  221.  
  222.  
  223. For DELETES, INSERTS, and CHANGES (but not MOVES) the old line and new lines
  224. are displayed as follows:
  225. < old line
  226. > new line
  227.  
  228.  */
  229.  
  230. #include <stdio.h>
  231. #include "stripnl.h"
  232.  
  233. /* choose SKIPCOUNT and BIGPRIME as follows:
  234.  * BIGPRIME > 2*MAXLINES in case both files have all unique lines
  235.  * such that SKIPCOUNT*tablesize probes will hit every slot in hash tbl
  236.  * (hint: use the hashtbl a.out to help you)
  237.  */
  238. #define MAXLINES 5000        /* max lines per file that can handle    */
  239. #define BIGPRIME 10001        /* ideally a prime number > 2*MAXLINES for hash into symtbl */
  240. #define _MAXLINE1 MAXLINES+2    /* two extra for first, last sentinel    */
  241. #define LINESIZE 1024        /* max chars per line            */
  242. #define _LINESIZE LINESIZE+2    /* two extra for '\n', '\0' fgets rtns    */
  243. #define SKIPCOUNT    4    /* reprobe into hash symbol table    */
  244. #define CHANGESEP    "---\n"    /* line separator for change block    */
  245. #define ZAPFLAG    1        /* 1 = yes, remove leading white space    */
  246.  
  247.  
  248.  
  249.  
  250. /* structure for old, new files.  One structure per line.
  251.  * An array oa for the old file, and an array na for the new file.
  252.  * If the line 'oldi' in the old file has NOT been matched to a line in
  253.  * the new file then oa[oldi].flag == L_SYMINDX.
  254.  * Similarly if the line 'newi' in the new file has NOT been matched to
  255.  * a line in the old file, then na[newi].flag == L_SYMINDX.
  256.  * When line 'oldi' in the old file has been matched to line 'newi'
  257.  * in the new file, then oa[oldi].flag == L_LINENUM,
  258.  * na[newi].flag == L_LINENUM, and each line points to the other, e.g.,
  259.  * oa[oldi].lineloc == newi, and na[newi].lineloc == oldi.
  260.  */
  261. struct linerec {
  262.     int lineloc;        /* line number in other file or symtbl index */
  263.     int flag;        /* tells which as defined below        */
  264.     };
  265. #define L_LINENUM 0
  266. #define L_SYMINDX 1
  267.  
  268.  
  269.  
  270. /* symbol table structure.  One per unique line in both files.        */
  271. /* the line is keyed into the array via a hash code            */
  272. struct symrec {
  273.     char    *stashline;    /* saved line in malloc'ed memory    */
  274.     int    ocount;        /* count of lines in old file, 0,1,many    */
  275.     int    ncount;        /* count of lines in new file, 0,1,many    */
  276.     int    olinenum;    /* line number in the old file        */
  277.     };
  278.  
  279.  
  280.  
  281.  
  282. /*globals */
  283. char    *cmd,            /* name of this command            */
  284.     errbuf [_LINESIZE],    /* build err msg for perror        */
  285.     linebuf [_LINESIZE],    /* read line from either file into here    */
  286.     runflag [26],        /* array of options flags set        */
  287.     *oldfile,        /* name of old file            */
  288.     *newfile;        /* name of new file            */
  289.  
  290. FILE    *oldfp,            /* stream for old file            */
  291.     *newfp;            /* stream for new file            */
  292.  
  293. struct linerec
  294.     oa [_MAXLINE1],        /* for old file                */
  295.     na [_MAXLINE1];        /* for new file                */
  296.  
  297. struct symrec
  298.     symtbl [BIGPRIME];    /* symbol table of all lines seen    */
  299.  
  300. int    lastnew,        /* total lines read from new file    */
  301.     lastold,        /* total lines in old file        */
  302.     numsymbols,        /* number of entries in symbol table    */
  303.     debug;            /* debug flag set by -d flag        */
  304.  
  305.  
  306.  
  307.  
  308. /* external non-integer functions */
  309. FILE    *fopen();        /* fopen (3)            */
  310. char    *malloc ();        /* malloc (3)            */
  311. char    *remwhite ();        /* remove white space from string */
  312.  
  313. /* internal non-integer functions */
  314. unsigned int hashline ();
  315.  
  316.  
  317. main (argc, argv)
  318.     int argc;
  319.     char **argv;
  320.  
  321. {
  322.     int    usage;        /* TRUE iff there is a usage error */
  323.  
  324.     /* name of command */
  325.     cmd = argv [0];
  326.  
  327.     /* check arguments and assign global file names */
  328.     usage = 0;        /* assume no usage error */
  329.     debug = 0;        /* assume no debugging wanted */
  330.     if (argc == 3)
  331.         {
  332.         oldfile = argv [1];
  333.         newfile = argv [2];
  334.         }
  335.     else if (argc == 4 && *argv[1] == '-')
  336.         {
  337.         register char *cp;
  338.         for (cp = argv[1]+1; *cp; ++cp)
  339.             if ('a' <= *cp && *cp <= 'z')
  340.                 switch (*cp) {
  341.                 case 'v':    /* verbose - debug */
  342.                 case 'd':    /* drop */
  343.                 case 'm':    /* monotonical by 1 */
  344.                 case 'c':    /* count */
  345.                 case 'w':    /* white space */
  346.                     if (*cp == 'v')
  347.                         debug = 1;
  348.                     runflag [*cp - 'a'] = 1;
  349.                     break;
  350.                 default:
  351.                     usage = 1;
  352.                     break;
  353.                 }
  354.             else
  355.                 usage = 1;
  356.         oldfile = argv[2];
  357.         newfile = argv[3];
  358.         }
  359.     else
  360.         usage = 1;
  361.  
  362.     if (usage)
  363.         {
  364.         fprintf (stderr, "usage: %s [-cdmvw] oldfile newfile\n", cmd);
  365.         exit (1);
  366.         }
  367.  
  368.  
  369.     /* open both files */
  370.     openfiles ();
  371.  
  372.     initvars ();
  373.  
  374.     src_compare ();
  375.  
  376.     /* close both files */
  377.     closefiles ();
  378.  
  379. }
  380.  
  381. initvars ()
  382. {
  383.     numsymbols = 0;
  384. }
  385.  
  386.  
  387.  
  388. /*
  389.  * compare the 2 files in 6 easy passes
  390.  */
  391.  
  392. src_compare ()
  393. {
  394.     pass1 ();    /* read, store new file                */
  395.     pass2 ();    /* read, store old file                */
  396.     pass3 ();    /* match up lines which occur only once        */
  397.     pass4 ();    /* apply rule 2 working toward end        */
  398.     pass5 ();    /* apply rule 2 working toward beginning    */
  399. /*    pass5a ();    /* convert block-moves to insert/deletes    */
  400. /*    dumparray ();    /* see if internal tables are built correctly    */
  401.     pass6 ();    /* print out differences            */
  402.     if (debug)
  403.         printf ("debug: symbol table: occupied = %d, total = %d\n",
  404.         numsymbols, BIGPRIME);
  405. }
  406.  
  407. /*
  408.  * pass 1
  409.  * read in new file.
  410.  */
  411.  
  412. pass1 ()
  413. {
  414.     int
  415.         linenum,    /* which line we are on            */
  416.         stat,        /* result from stripnl            */
  417.         sindex;        /* index into symbol table        */
  418.     char    *cp;        /* char pointer into line        */
  419.  
  420.  
  421.  
  422.     /* read each line of new file in a loop.        */
  423.     /* stop if eof or can't handle that many lines        */
  424.     for (linenum = 0;
  425.         fgets (linebuf, sizeof(linebuf), newfp) != (char *)NULL &&
  426.         ++linenum <= MAXLINES; )
  427.         {
  428.  
  429.         /* strip newline at end and make sure line wasn't too long */
  430.         stat = stripnl (linebuf, sizeof(linebuf) );
  431.  
  432.         if (stat == L_SUCCESS)
  433.             ;
  434.         else if (stat == L_BADFORM)
  435.             fprintf (stderr, "%s: Warning, line %d in file %s not terminated with newline\n",
  436.             cmd, linenum, newfile);
  437.         else
  438.             {
  439.             fprintf (stderr, "%s: line %d longer than %d chars in file %s\n",
  440.             cmd, linenum, LINESIZE, newfile);
  441.             exit (1);
  442.             }
  443.  
  444.         /* if compressing white space, then compress into line buf */
  445.         if (runflag ['w' - 'a'] )
  446.             {
  447.             char *cp;
  448.             cp = remwhite (linebuf, ZAPFLAG);
  449.             strcpy (linebuf, cp);
  450.             }
  451.  
  452.         sindex = addsymbol (linebuf);    /* put line into symbol tbl */
  453.         if (symtbl [sindex].ncount < 2)
  454.             ++symtbl [sindex].ncount;
  455.         na [linenum].lineloc = sindex;
  456.         na [linenum].flag = L_SYMINDX;
  457.         }
  458.  
  459.     /* see if new file was empty */
  460.     if (linenum == 0)
  461.         {
  462.         fprintf (stderr, "%s:  New file %s is empty.  Diff is delete entire old file.\n", newfile, cmd);
  463.         exit (1);
  464.         }
  465.  
  466.     if (linenum > MAXLINES)
  467.         {
  468.         fprintf (stderr, "%s:  New file %s is too big.  Last line read was %d.\n", cmd, newfile, MAXLINES);
  469.         exit (1);
  470.         }
  471.  
  472.     /* assign global number of new lines */
  473.     lastnew = linenum;
  474. }
  475.  
  476.  
  477. /*
  478.  * pass 2
  479.  * read in old file.
  480.  */
  481.  
  482. pass2 ()
  483. {
  484.     int
  485.         linenum,    /* which linenum we are on        */
  486.         stat,        /* result from stripnl            */
  487.         sindex;        /* index into symbol table        */
  488.     char    *cp;        /* char pointer into line        */
  489.  
  490.  
  491.  
  492.     /* read each line of old file in a loop.        */
  493.     /* stop if eof or can't handle that many lines        */
  494.     for (linenum = 0;
  495.         fgets (linebuf, sizeof(linebuf), oldfp) != (char *)NULL &&
  496.         ++linenum <= MAXLINES; )
  497.         {
  498.  
  499. #if 0        /* old way */
  500.         /* strip newline at end and make sure line wasn't too long */
  501.         cp = &linebuf[strlen(linebuf)-1];
  502.         if (*cp == '\n')
  503.             *cp = '\0';
  504.         else if (strlen(linebuf) < sizeof(linebuf)-1)
  505.             fprintf (stderr, "%s: Warning, line %d in file %s not terminated with newline\n", cmd, linenum, oldfile);
  506.         else
  507.             {
  508.             fprintf (stderr, "%s: line %d longer than %d chars in file %s\n",
  509.                 cmd, linenum, LINESIZE, oldfile);
  510.             exit (1);
  511.             }
  512. #endif
  513.  
  514.         /* strip newline at end and make sure line wasn't too long */
  515.         stat = stripnl (linebuf, sizeof(linebuf) );
  516.  
  517.         if (stat == L_SUCCESS)
  518.             ;
  519.         else if (stat == L_BADFORM)
  520.             fprintf (stderr, "%s: Warning, line %d in file %s not terminated with newline\n",
  521.             cmd, linenum, oldfile);
  522.         else
  523.             {
  524.             fprintf (stderr, "%s: line %d longer than %d chars in file %s\n",
  525.             cmd, linenum, LINESIZE, oldfile);
  526.             exit (1);
  527.             }
  528.  
  529.  
  530.         /* if compressing white space, then compress into line buf */
  531.         if (runflag ['w' - 'a'] )
  532.             {
  533.             char *cp;
  534.             cp = remwhite (linebuf, ZAPFLAG);
  535.             strcpy (linebuf, cp);
  536.             }
  537.  
  538.         sindex = addsymbol (linebuf);    /* put line into symbol tbl */
  539.         if (symtbl [sindex].ocount < 2)
  540.             ++symtbl [sindex].ocount;
  541.         symtbl[sindex].olinenum = linenum;
  542.         oa [linenum].lineloc = sindex;
  543.         oa [linenum].flag = L_SYMINDX;
  544.         }
  545.  
  546.     /* see if old file was empty */
  547.     if (linenum == 0)
  548.         {
  549.         fprintf (stderr, "%s:  Old file %s is empty.  Diff is add entire new file.\n", oldfile, cmd);
  550.         exit (1);
  551.         }
  552.  
  553.     if (linenum > MAXLINES)
  554.         {
  555.         fprintf (stderr, "%s:  Old file %s is too big.  Last line read was %d.\n", cmd, oldfile, MAXLINES);
  556.         exit (1);
  557.         }
  558.  
  559.     /* assign number of lines in old file */
  560.     lastold = linenum;
  561. }
  562.  
  563.  
  564. /*
  565.  * Add a line to the symbol table.
  566.  * The hash function determines the initial probe into the symbol table.
  567.  * If the line is new, then core is malloc'ed for storage, and
  568.  * the 'value' is the pointer to the line (empty slot can be found).
  569.  * If the line is old, the old index is returned.
  570.  *
  571.  * returns
  572.  *    index into symbol table
  573.  *    updated global 'numsymbols' for debugging.
  574.  *
  575.  */
  576. addsymbol (line)
  577.     char *line;
  578. {
  579.     int    sindex,        /* symbol table index            */
  580.         firstprobe;    /* index of first probe into symbol tbl    */
  581.     char    *cp;        /* malloc char pointer            */
  582.  
  583.     sindex = firstprobe = hashline (line, BIGPRIME);
  584.  
  585.     /* keep looping until empty slot found or table is full.    */
  586.     /* table cannot be full.                    */
  587.     while (1)
  588.         {
  589.         /* if find an empty slot, add the line there.        */
  590.         if (symtbl [sindex].stashline == (char *)NULL)
  591.             {
  592.             cp = malloc (strlen (linebuf) + 1);
  593.             if (cp == (char *)NULL)
  594.                 {
  595.                 fprintf (stderr, "%s: out of space in function addsymbol\n", cmd);
  596.                 exit (1);
  597.                 }
  598.  
  599.             /* copy the line to storage area        */
  600.             strcpy (cp, line);
  601.  
  602.             /* save the line in the symbol table entry    */
  603.             symtbl [sindex].stashline = cp;
  604.  
  605.             ++numsymbols;
  606.  
  607.             break;
  608.             }
  609.  
  610.         /* if the line is already in the table, then done */
  611.         else if (strcmp (symtbl [sindex].stashline, line) == 0)
  612.             break;
  613.  
  614.         /* else it's a collision with a different line, so
  615.          * let's do linear open addressing.  That is, reprobe
  616.          * SKIPCOUNT slots below, modulo the table size.
  617.          * SKIPCOUNT == 1 means primaray clustering.
  618.          * SKIPCOUNT > 1 means secondary clustering.
  619.          * Check for overflow.
  620.          */
  621.         else
  622.             {
  623.             sindex += SKIPCOUNT;
  624.             if (sindex >= BIGPRIME)
  625.                 sindex = 0;        /* wraparound */
  626.             if (sindex == firstprobe)
  627.                 {
  628.                 fprintf (stderr, "%s: symtbl overflow!\n", cmd);
  629.                 exit (1);
  630.                 }
  631.             }
  632.         }
  633.  
  634.  
  635.     return sindex;
  636. }
  637.  
  638.  
  639. /*
  640.  * pass 3.
  641.  * Process NA array and link lines up which appear only once
  642.  * in both files.
  643.  * Link virtual line pointer at front and end of both files.
  644.  */
  645.  
  646. pass3 ()
  647. {
  648.     int    newi,        /* loop counter thru na array        */
  649.         oldi,        /* index into oa array            */
  650.         symi;        /* index into symbol table array    */
  651.  
  652.     /* loop thru all new lines.  Those that occur once are linked to
  653.      * each other instead of to the symbol table as they used to be.
  654.      */
  655.     for (newi = 1; newi <= lastnew; ++newi)
  656.         {
  657.         symi = na[newi].lineloc;    /* get symbol tbl index    */
  658.         if ((symtbl[symi].ocount == 1) && (symtbl[symi].ncount == 1))
  659.             {
  660.             oldi = symtbl[symi].olinenum;
  661.             linkup (oldi, newi);
  662.             }
  663.         }
  664.  
  665.     /* link the virtual line 'begin' of each file to each other */
  666.     linkup (0, 0);
  667.  
  668.     /* line the virtual line 'end' of each file to each other */
  669.     linkup (lastold+1, lastnew+1);
  670. }
  671.  
  672.  
  673. /*
  674.  * pass 4
  675.  * loop ascending thru new lines in na array.
  676.  * If line newi in new file is linked to line oldi in old file,
  677.  * but the next lines of each contain the same symbol table
  678.  * pointer, then link na[newi+1] to oa[oldi+1].
  679.  */
  680. pass4 ()
  681. {
  682.     int    newi,
  683.         oldi;
  684.  
  685.     /* process 'begin', all lines in new file, but NOT virtual 'end' */
  686.     for (newi = 0; newi <= lastnew; ++newi)
  687.         {
  688.         if (na[newi].flag == L_LINENUM)
  689.             {
  690.             oldi = na[newi].lineloc;
  691.             if ((na[newi+1].flag == L_SYMINDX) &&
  692.                 (oa[oldi+1].flag == L_SYMINDX) &&
  693.                 (na[newi+1].lineloc == oa[oldi+1].lineloc))
  694.                 linkup (oldi+1, newi+1);
  695.             }
  696.         }
  697. }
  698.  
  699.  
  700. /*
  701.  * pass 5
  702.  * Process new file in descending order.
  703.  * Similar to pass 4, but in reverse order.
  704.  */
  705. pass5 ()
  706. {
  707.     int    newi,
  708.         oldi;
  709.  
  710.     /* process 'end', all lines in new file, but NOT virtual 'begin' */
  711.     for (newi = lastnew+1; newi > 0; --newi)
  712.         {
  713.         if (na[newi].flag == L_LINENUM)
  714.             {
  715.             oldi = na[newi].lineloc;
  716.             if ((na[newi-1].flag == L_SYMINDX) &&
  717.                 (oa[oldi-1].flag == L_SYMINDX) &&
  718.                 (na[newi-1].lineloc == oa[oldi-1].lineloc))
  719.                 linkup (oldi-1, newi-1);
  720.             }
  721.         }
  722.  
  723.  
  724. }
  725.  
  726.  
  727. /*
  728.  * pass 6
  729.  * output the differences.
  730.  */
  731. pass6 ()
  732. {
  733.     int    oldi,        /* current line number in old file    */
  734.         newi,        /* current line number in new file    */
  735.         oldmatch,    /* true iff old line matches SOME line in new file */
  736.         newmatch,    /* true iff new line matches SOME line in old file */
  737.         omatcount,    /* match count in old file        */
  738.         nmatcount,    /* match count in new file        */
  739.         odrop,        /* old file "relative drop" of new line */
  740.         ndrop,        /* new file "relative drop" of old line */
  741.         ocomp,        /* comparison result for old file    */
  742.         ncomp,        /* comparison result for new file    */
  743.         ospan,        /* size of old monotonical block    */
  744.         nspan;        /* size of new monotonical block    */
  745.  
  746.     for (oldi = 0, newi = 0; oldi <= lastold+1 && newi <= lastnew+1;)
  747.         {
  748.  
  749.         /* set flags to indicate if each line is linked
  750.          * to another line in the other file.
  751.          */
  752.  
  753.         /* is old line linked to another line in the new file? */
  754.         oldmatch = (oa[oldi].flag == L_LINENUM);
  755.  
  756.         /* is new line linked to another line in the old file? */
  757.         newmatch = (na[newi].flag == L_LINENUM);
  758.  
  759.  
  760.         /* if old line moved from old file up (toward begin) in
  761.          * new file, then we have already processed the block
  762.          * move in the new file.  Just skip the line in the old file.
  763.          */
  764.         if (oa[oldi].lineloc < newi && oldmatch)
  765.             {
  766.             ++oldi;
  767.             continue;
  768.             }
  769.  
  770.         /* if old line moved from old file down (toward end) in
  771.          * old file, then we we have already processed the block
  772.          * move in the old file.  Just skip the line in the new file.
  773.          */
  774.         else if (na[newi].lineloc < oldi && newmatch)
  775.             {
  776.             ++newi;
  777.             continue;
  778.             }
  779.  
  780.  
  781.         /* there are four combinations of booleans oldmatch and newmatch */
  782.  
  783.         /* if both lines are linked to SOME line in the other file */
  784.         if (oldmatch && newmatch)
  785.             {
  786.             /* if both lines match each other, then go
  787.              * to next line in both files
  788.              */
  789.             if (oa[oldi].lineloc == newi)
  790.                 {
  791.                 if (debug)
  792.                     printf ("debug: Same old line %d and new line %d\n", oldi, newi);
  793.                 ++oldi;
  794.                 ++newi;
  795.                 continue;
  796.                 }
  797.  
  798.             /* blocks not linked to each other.
  799.              * If there are more lines in oldfile that
  800.              * are monotonically increasing by one in
  801.              * the new file, then this is normal, and the
  802.              * new block is moved down in the old file.
  803.              * If there are more lines in newfile that
  804.              * are monotonically increasing by one in
  805.              * the old file, then this is normal, and
  806.              * the old block is moved down in the new file.
  807.              */
  808.  
  809.             /* get size of old block which is monitonically
  810.              * increasing by one in the new file.
  811.              */
  812.             ospan = oldmon (oldi);
  813.  
  814.             /* get size of new block which is monitonically
  815.              * increasing by one in the old file.
  816.              */
  817.             nspan = newmon (newi);
  818.  
  819.             /* count the number of lines in the old file between
  820.              * the current line and the line which corresponds
  821.              * to the first new moved line.
  822.              */
  823.             omatcount = gomatch (oldi, na[newi].lineloc);
  824.  
  825.             /* count the number of lines in the new file between
  826.              * the current line and the old moved line which
  827.              * match.
  828.              */
  829.             nmatcount = gnmatch (newi, oa[oldi].lineloc);
  830.  
  831.             /* get number of old lines the new block drops down
  832.              * into the old file.  If old drop is < new drop
  833.              * then the old block has moved down further into
  834.              * the new file than the new block has moved down
  835.              * into the old file.  The relative steepness of the
  836.              * slope of the line from oldi to its matched line
  837.              * is more than the steepnes of the other slope,
  838.              * and since line don't usually move far, assume
  839.              * that the new to old move is a match, and the
  840.              * old to new is an old block moved down.
  841.              */
  842.             odrop = na [newi].lineloc - oldi;
  843.  
  844.             /* same for new file */
  845.             ndrop = oa [oldi].lineloc - newi;
  846.  
  847.             /* if 'd' flag is set, use 'drop' for match */
  848.             if (runflag ['d' - 'a'])
  849.                 {
  850.                 ocomp = odrop;
  851.                 ncomp = ndrop;
  852.                 }
  853.             /* if 'm' flag set, use bigger monotonically increasing
  854.              * by 1 span
  855.              */
  856.             else if (runflag ['m' - 'a'])
  857.                 {
  858.                 ocomp = ospan;
  859.                 ncomp = nspan;
  860.                 }
  861.             /* if 'c' flag then use match count */
  862.             else if (runflag ['c' - 'a'])
  863.                 {
  864.                 ocomp = omatcount;
  865.                 ncomp = nmatcount;
  866.                 }
  867.             /* default - best one */
  868.             else
  869.                 {
  870.                 ocomp = omatcount;
  871.                 ncomp = nmatcount;
  872.                 }
  873.  
  874.  
  875.  
  876.             if (ocomp < ncomp)        /* old block moved down */
  877.                 eatold (&oldi, ospan);    /* eat old mv'ed blk */
  878.             else                /* new block moved down */
  879.                 eatnew (&newi, nspan);    /* eat new mv'ed blk */
  880.             }
  881.  
  882.         /* new lines added (inserted) into new file */
  883.         else if (oldmatch && !newmatch)
  884.             newinsert (oldi, &newi); /* skip new insert blk */
  885.  
  886.         /* old lines deleted from old file */
  887.         else if (!oldmatch && newmatch)
  888.             olddelete (&oldi, newi);    /* skip old delete block */
  889.  
  890.         /* old lines changed into new file */
  891.         else    /* !oldmatch && !newmatch */
  892.             oldchange (&oldi, &newi); /* skip old delete block and new insert block */
  893.         }
  894. }
  895.  
  896. /*
  897.  * block of old lines beginning at linenum 'oldi' are matched with
  898.  * a block of new lines.  Count the number of lines in the old block
  899.  * which are monotonically increasing by one in the new file.
  900.  * returns -
  901.  *    size of old block
  902.  */
  903. oldmon (oldi)
  904.     int    oldi;
  905. {
  906.     int    osize,        /* size of old block            */
  907.         expnew,        /* line number expected in new file    */
  908.         curoldnum;    /* current line number in old file    */
  909.  
  910.  
  911.     curoldnum = oldi;    /* save old line number so can tell
  912.                  * how big the old block is at the end
  913.                  */
  914.  
  915.     do
  916.         {
  917.         expnew = oa[curoldnum].lineloc + 1;
  918.         ++curoldnum;
  919.         }
  920.     while ((curoldnum <= lastold+1)            /* in bounds */
  921.         && (expnew == oa[curoldnum].lineloc)    /* monotonical by 1 */
  922.         && (oa[curoldnum].flag == L_LINENUM));    /* match */
  923.  
  924.     osize = curoldnum - oldi;
  925.  
  926.     if (debug)
  927.         printf ("debug: lines %d-%d of old file are monotonical\n", oldi, curoldnum-1);
  928.  
  929.     return osize;
  930. }
  931.  
  932.  
  933. newmon (newi)
  934.     int    newi;
  935. {
  936.     int    nsize,        /* size of new block            */
  937.         expold,        /* line number expected in old file    */
  938.         curnewnum;    /* current line number in new file    */
  939.  
  940.  
  941.     curnewnum = newi;    /* save new line number so can tell
  942.                  * how big the new block is at the end
  943.                  */
  944.  
  945.     do
  946.         {
  947.         expold = na[curnewnum].lineloc + 1;
  948.         ++curnewnum;
  949.         }
  950.     while ((curnewnum <= lastnew+1)            /* in bounds */
  951.         && (expold == na[curnewnum].lineloc)    /* monotonical by 1 */
  952.         && (na[curnewnum].flag == L_LINENUM));    /* match */
  953.  
  954.     nsize = curnewnum - newi;
  955.  
  956.     if (debug)
  957.         printf ("debug: lines %d-%d of new file are monotonical\n", newi, curnewnum-1);
  958.  
  959.     return nsize;
  960. }
  961.  
  962.  
  963. /*
  964.  * eat old block beginning with old line number *'oldi' and 'ospan' lines
  965.  * These old lines are moved down into the new file.
  966.  * The output format is
  967. 5,6m7,8        // old lines 5-6 are moved to new lines 7-8
  968. 5m7        // old line 5 is moved to new line 7
  969.  * returns
  970.  *    *oldi = updated old line number
  971.  */
  972. eatold (oldi, ospan)
  973.     int    *oldi,
  974.         ospan;
  975. {
  976.     int    newi;
  977.  
  978.     /* get starting line number of new block */
  979.     newi = oa[*oldi].lineloc;
  980.  
  981.     /* how many lines in the old block - one or more? */
  982.     if (ospan == 1)
  983.         printf ("%dm%d\n", *oldi, newi);
  984.     else if (ospan > 1)
  985.         printf ("%d,%dm%d,%d\n", *oldi, *oldi+ospan-1, newi, newi+ospan-1);
  986.     else
  987.         {
  988.         fprintf (stderr, "%s: unexpected negative ospan = %d in function eatold\n", ospan);
  989.         exit (1);
  990.         }
  991.  
  992.     /* return old line number after the old moved block */
  993.     *oldi += ospan;
  994.  
  995. }
  996.  
  997.  
  998. /*
  999.  * eat the new block
  1000.  * Like eatold, but works on the new block.
  1001.  */
  1002.  
  1003. eatnew (newi, nspan)
  1004.     int    *newi,
  1005.         nspan;
  1006. {
  1007.     int    oldi;
  1008.  
  1009.     /* get starting line number in the old file */
  1010.     oldi = na[*newi].lineloc;
  1011.  
  1012.     if (nspan == 1)
  1013.         printf ("%dm%d\n", oldi, *newi);
  1014.     else if (nspan > 1)
  1015.         printf ("%d,%dm%d,%d\n", oldi, oldi+nspan-1, *newi, *newi+nspan-1);
  1016.     else
  1017.         {
  1018.         fprintf (stderr, "%s: unexpected negative nspan = %d in function eatnew\n", nspan);
  1019.         exit (1);
  1020.         }
  1021.  
  1022.     *newi += nspan;
  1023. }
  1024.  
  1025. /*
  1026.  * Print new lines inserted in old file to transform into new file
  1027.  * input
  1028.  *    oldi - one after the current old line number !!!!!!!
  1029.  *    *newi - first line number in new file of inserted line.
  1030.  * output
  1031.  *    *newi - next line number in new file after inserted block.
  1032.  *    printed lines of the form
  1033.  *
  1034.  
  1035. 5a7        // after old line 5 add one newline as newline 7
  1036. > new line 8
  1037.  
  1038.  * or
  1039.  
  1040. 5a7,8        // after old line 5 add two newlines as newline 7 and 8
  1041. > new line 7
  1042. > new line 8
  1043.  
  1044.  */
  1045. newinsert (oldi, newi)
  1046.     int    oldi,
  1047.         *newi;
  1048. {
  1049.     int    nsize,        /* number of lines inserted in new file    */
  1050.         csize,        /* current number of lines in a loop    */
  1051.         curnewline;    /* current line number in new file    */
  1052.  
  1053.     if (debug)
  1054.         printf ("debug: Found New Insert.  Old line %d.  New line %d.\n", oldi, *newi);
  1055.  
  1056.     /* first compute size so we know which format to use (single line
  1057.      * insert or multiline insert)
  1058.      * Get the number of lines in the insert block.
  1059.      */
  1060.     nsize = inssize (*newi);
  1061.  
  1062.     if (nsize == 1)
  1063.         printf ("%da%d\n", oldi-1, *newi);
  1064.     else if (nsize > 1)
  1065.         printf ("%da%d,%d\n", oldi-1, *newi, *newi+nsize-1);
  1066.     else
  1067.         {
  1068.         fprintf (stderr, "%s: unexpected new block size = %d in function newinsert\n", nsize);
  1069.         exit (1);
  1070.         }
  1071.  
  1072.     /* print the new inserted lines */
  1073.     for (curnewline = *newi, csize = nsize; csize > 0; ++curnewline, --csize)
  1074.         printf ("> %s\n", symtbl [ na[curnewline].lineloc ].stashline);
  1075.  
  1076.     /* return the new line */
  1077.     *newi += nsize;
  1078. }
  1079.  
  1080.  
  1081.  
  1082.  
  1083. /*
  1084.  * Print that a group of lines in the old file was deleted
  1085.  * input -
  1086.  *    *oldi - line number in old file where the group of lines begins
  1087.  *    newi - line number + 1 in new file after which the delete occurs.
  1088.  * output
  1089.  *    *oldi - updated with the next old line after the delete block
  1090. 5d7        // old line 5 deleted after new line 7
  1091. < old line 5
  1092. 5,6d7        // old lines 5 and 6 deleted after new line 7
  1093. < old line 5
  1094. < old line 6
  1095.  *
  1096.  */
  1097.  
  1098. olddelete (oldi, newi)
  1099.     int    *oldi,
  1100.         newi;
  1101. {
  1102.     int    osize,        /* number of lines deleted in old file    */
  1103.         csize,        /* current size in in the loop        */
  1104.         curoldline;    /* current line number in old file    */
  1105.  
  1106.     if (debug)
  1107.         printf ("debug: Found Old Delete.  Old line %d.  New line %d.\n", *oldi, newi);
  1108.  
  1109.     /* first compute size so we know which format to use (single line
  1110.      * insert or multiline delete)
  1111.      * Get the number of lines in the old delete block.
  1112.      */
  1113.     osize = delsize (*oldi);
  1114.  
  1115.  
  1116.     /* print the header for the line deletes */
  1117.     if (osize == 1)
  1118.         printf ("%dd%d\n", *oldi, newi-1);
  1119.     else if (osize > 1)
  1120.         printf ("%d,%dd%d\n", *oldi, *oldi+osize-1, newi-1);
  1121.     else
  1122.         {
  1123.         fprintf (stderr, "%s: unexpected old block size = %d in function olddelete\n", osize);
  1124.         exit (1);
  1125.         }
  1126.  
  1127.     /* print the old deleted lines */
  1128.     for (curoldline = *oldi, csize = osize; csize > 0; ++curoldline, --csize)
  1129.         printf ("< %s\n", symtbl [ oa[curoldline].lineloc ].stashline);
  1130.  
  1131.     /* return the old line after the delete block */
  1132.     *oldi += osize;
  1133. }
  1134.  
  1135.  
  1136.  
  1137.  
  1138. /*
  1139.  * Print that a group of old lines has been updated to a group of new lines.
  1140.  * input
  1141.  *    *oldi = line number of start of old lines
  1142.  *    *newi = line number of start of new lines
  1143.  * output
  1144.  *    *oldi = line number after block deleted in the old file
  1145.  *    *newi = line number after block inserted in the new file
  1146.  *    print statements according to one of 4 forms:
  1147. startold c startnew
  1148. startold c startnew,endnew
  1149. startold,endold c startnew
  1150. startold,endold c startnew,endnew
  1151.  * Examples
  1152. 5c7        // old line 5 has been replace by new line 7
  1153. < old line 5
  1154. ---
  1155. > new line 7
  1156.  
  1157. 5,6c7,8        // old lines 5 and 6 have been replaced by new lines 7 and 8
  1158. < old line 5
  1159. < old line 6
  1160. ---
  1161. > new line 7
  1162. > new line 8
  1163.  */
  1164.  
  1165. oldchange (oldi, newi)
  1166.     int    *oldi,
  1167.         *newi;
  1168. {
  1169.     int    curold,        /* current line number in old file    */
  1170.         curnew,        /* current line number in new file    */
  1171.         osize,        /* size of block changed in old file    */
  1172.         nsize,        /* size of block changed in new file    */
  1173.         csize,        /* current block size for the loop    */
  1174.         curoldline,    /* current line number in old file    */
  1175.         curnewline;    /* current line number in new file    */
  1176.  
  1177.     if (debug)
  1178.         printf ("debug: Found Changed Lines.  Old line %d.  New line %d\n", *oldi, *newi);
  1179.  
  1180.     /* get the size of the old deleted block and the new inserted block */
  1181.     osize = delsize (*oldi);
  1182.     nsize = inssize (*newi);
  1183.  
  1184.     /* print the header for the old deleted block */
  1185.     if (osize == 1)
  1186.         printf ("%dc", *oldi);
  1187.     else if (osize > 1)
  1188.         printf ("%d,%dc", *oldi, (*oldi)+osize-1);
  1189.     else
  1190.         {
  1191.         fprintf (stderr, "%s: unexpected old block size = %d in function oldchange\n", osize);
  1192.         exit (1);
  1193.         }
  1194.  
  1195.     /* print the header for the new inserted block */
  1196.     if (nsize == 1)
  1197.         printf ("%d\n", *newi);
  1198.     else if (nsize > 1)
  1199.         printf ("%d,%d\n", *newi, (*newi)+nsize-1);
  1200.     else
  1201.         {
  1202.         fprintf (stderr, "%s: unexpected new block size = %d in function oldchange\n", nsize);
  1203.         exit (1);
  1204.         }
  1205.  
  1206.     /* Now print the old changed (delete) lines */
  1207.     for (curoldline = *oldi, csize = osize; csize > 0; ++curoldline, --csize)
  1208.         printf ("< %s\n", symtbl [ oa[curoldline].lineloc ].stashline);
  1209.  
  1210.     /* print line change separator */
  1211.     printf (CHANGESEP);
  1212.  
  1213.     /* Now print the new changed (inserted) lines */
  1214.     for (curnewline = *newi, csize = nsize; csize > 0; ++curnewline, --csize)
  1215.         printf ("> %s\n", symtbl [ na[curnewline].lineloc ].stashline);
  1216.  
  1217.     /* return the new old and new lines */
  1218.     *oldi += osize;
  1219.     *newi += nsize;
  1220. }
  1221.  
  1222.  
  1223.  
  1224. /*
  1225.  * these next two routines are called upon by functions
  1226.  *    olddelete, newinsert, and oldchange
  1227.  */
  1228.  
  1229. /*
  1230.  * starting with line number 'newi' in the new file, count the number of
  1231.  * lines in the insert block.
  1232.  *
  1233.  * Loop thru the insert block.  The block is a series of new lines
  1234.  * that aren't linked to lines in the old file.  That is, each
  1235.  * inserted line points to a symbol table entry.
  1236.  */
  1237. inssize (newi)
  1238.     int    newi;
  1239. {
  1240.     register
  1241.     int    curnewline,        /* current line number in new file    */
  1242.         nsize;            /* number of new lines in insert block    */
  1243.  
  1244.  
  1245.     curnewline = newi;
  1246.     while (curnewline <= lastnew+1 && na[curnewline].flag == L_SYMINDX)
  1247.         ++curnewline;
  1248.  
  1249.     /* curnewline is now the new line number AFTER the insert block */
  1250.  
  1251.     /* compute the number of lines in the insert block */
  1252.     nsize = curnewline - newi;
  1253.  
  1254.     if (debug)
  1255.         printf ("debug: at new line %d, the insert block has %d lines\n", newi, nsize);
  1256.  
  1257.     return nsize;
  1258. }
  1259.  
  1260.  
  1261.  
  1262. /*
  1263.  * compute the number of lines in the old delete block beginning
  1264.  * with old line number 'oldi' and return it.
  1265.  *
  1266.  * Loop thru the delete block.  The block is a series of old lines
  1267.  * that aren't linked to lines in the new file.  That is, each
  1268.  * deleted line points to a symbol table entry.
  1269.  */
  1270.  
  1271. delsize (oldi)
  1272.     int oldi;
  1273. {
  1274.     register
  1275.     int    curoldline,    /* current line number in old file    */
  1276.         osize;        /* number of old lines in delete block    */
  1277.  
  1278.     curoldline = oldi;
  1279.     while (curoldline <= lastold+1 && oa[curoldline].flag == L_SYMINDX)
  1280.         ++curoldline;
  1281.  
  1282.     /* curoldline is now the old line number AFTER the delete block */
  1283.  
  1284.     /* compute the number of lines in the delete block */
  1285.     osize = curoldline - oldi;
  1286.  
  1287.     if (debug)
  1288.         printf ("debug: at old line %d, the delete block has %d lines\n", oldi, osize);
  1289.  
  1290.     /* return the delete block size */
  1291.     return osize;
  1292. }
  1293.  
  1294.  
  1295.  
  1296.  
  1297.  
  1298.  
  1299. /*
  1300.  * dump the oa and na internal arrays which is the crudest way
  1301.  * to print the file comparisons.
  1302.  * This routine may be called in lieu of pass 6 as a debugging tool.
  1303.  */
  1304. dumparray ()
  1305. {
  1306.     int    oldi,
  1307.         newi;
  1308.  
  1309.     for (oldi = 0; oldi <= lastold+1; ++oldi)
  1310.         if (oa[oldi].flag == L_LINENUM)
  1311.             printf ("oa[%d] = %d\n", oldi, oa[oldi].lineloc);
  1312.         else
  1313.             printf ("oa[%d] INSERTED.\n", oldi);
  1314.  
  1315.  
  1316.     for (newi = 0; newi <= lastnew+1; ++newi)
  1317.         if (na[newi].flag == L_LINENUM)
  1318.             printf ("na[%d] = %d\n", newi, na[newi].lineloc);
  1319.         else
  1320.             printf ("na[%d] DELETED.\n", newi);
  1321. }
  1322.  
  1323.  
  1324.  
  1325. /* borrowed from hashname.c
  1326.  * eventually will be removed.
  1327.  */
  1328.  
  1329. unsigned int hashline (name,modval)
  1330.  
  1331.     register char *name;
  1332.     register unsigned int modval;
  1333.  
  1334. {
  1335.     register unsigned int i;
  1336.  
  1337.     i=0;
  1338.     while (*name != '\0'){
  1339.         i=((i<<2)+(*name&~040))%modval;
  1340.  
  1341.         name++;
  1342.         }
  1343.  
  1344.     return(i);
  1345. }
  1346.  
  1347.  
  1348.  
  1349. /*
  1350.  * linkup line oldi in old file to line newi' in new file
  1351.  */
  1352. linkup (oldi, newi)
  1353.     int    oldi,
  1354.         newi;
  1355. {
  1356.     oa[oldi].lineloc = newi;
  1357.     oa[oldi].flag = L_LINENUM;
  1358.     na[newi].lineloc = oldi;
  1359.     na[newi].flag = L_LINENUM;
  1360. }
  1361.  
  1362.  
  1363. /*
  1364.  * pass 5a converts block moves to delete/insert pairs
  1365.  */
  1366. pass5a ()
  1367. {
  1368.     int    oldi,
  1369.         newi;
  1370.  
  1371.     for (oldi = 1, newi = 1; oldi <= lastold+1; )
  1372.         {
  1373.         while (oa[oldi].flag == L_SYMINDX && oldi <= lastold+1)
  1374.             ++oldi;        /* skip deletes in old file    */
  1375.         while (na[newi].flag == L_SYMINDX && newi <= lastnew+1)
  1376.             ++newi;        /* skip inserts in new file    */
  1377.         if (oldi > lastold+1)
  1378.             break;
  1379.         if (newi > lastnew+1)
  1380.             break;
  1381.  
  1382.         if (oa[oldi].lineloc == newi)    /* begin matching lines */
  1383.             {
  1384.             oldi++;
  1385.             newi++;
  1386.             }
  1387.         else                /* discontinuity ?*/
  1388.             {
  1389.             if (oa[oldi].lineloc != lastnew+1)
  1390.                 resolve (oldi, newi);    /* yes */
  1391.             else
  1392.                 ;            /* no, sentinel */
  1393.             }
  1394.         }
  1395. }
  1396.  
  1397.  
  1398. resolve (oldi, newi)
  1399.     int    oldi,
  1400.         newi;
  1401.  
  1402. {
  1403.     int    xo, xn;
  1404.     int    t, ospan, nspan;
  1405.     int    symi;
  1406.  
  1407.     /* measure block starting at oa[oldi] */
  1408.     xo = oldi;
  1409.     do
  1410.         {
  1411.         t = 1 + oa[xo].lineloc;
  1412.         xo++;
  1413.         }
  1414.     while (t != oa[xo].lineloc);
  1415.     ospan = xo - oldi;
  1416.  
  1417.     /* measure block starting at na[newi] */
  1418.     xn = newi;
  1419.     do
  1420.         {
  1421.         t = 1 + na[xn].lineloc;
  1422.         xn++;
  1423.         }
  1424.     while (t != na[xn].lineloc);
  1425.     nspan = xn - newi;
  1426.  
  1427.  
  1428.  
  1429.     if (ospan < nspan)
  1430.         {
  1431.         xo = oldi;
  1432.         xn = oa[oldi].lineloc;
  1433.         t = ospan;
  1434.         oldi = oldi + ospan;
  1435.         }
  1436.     else
  1437.         {
  1438.         xn = newi;
  1439.         xo = na[newi].lineloc;
  1440.         t = nspan;
  1441.         newi = newi + nspan;
  1442.         }
  1443.  
  1444.     while (t > 0)
  1445.         {
  1446.         symi = 0;
  1447.         while (symi < BIGPRIME && symtbl[symi].olinenum != xo)
  1448.             symi++;
  1449.  
  1450.         if (symi >= BIGPRIME)
  1451.             {
  1452.             fprintf (stderr, "%s: can't find old line %d in symtbl\n", cmd, xo);
  1453.             dumpsym ();
  1454.             exit (1);
  1455.             }
  1456.  
  1457.  
  1458.         /* link the lines to the same symbol tbl entry */
  1459.         oa[xo].flag = L_SYMINDX;
  1460.         oa[xo].lineloc = symi;
  1461.         na[xn].flag = L_SYMINDX;
  1462.         na[xn].lineloc = symi;
  1463.  
  1464.         ++xo;
  1465.         ++xn;
  1466.         --t;
  1467.         }
  1468. }
  1469.  
  1470. /*
  1471.  * open global files 'oldfile' and 'newfile'
  1472.  */
  1473. openfiles ()
  1474. {
  1475.     /* open old source file for reading */
  1476.     oldfp = fopen (oldfile, "r");
  1477.     if (oldfp == (FILE *)NULL)
  1478.         {
  1479.         sprintf (errbuf, "%s: can't oldfile open %s", cmd, oldfile);
  1480.         perror (errbuf);
  1481.         exit (1);
  1482.         }
  1483.  
  1484.  
  1485.  
  1486.  
  1487.     /* open new source file for reading */
  1488.     newfp = fopen (newfile, "r");
  1489.     if (newfp == (FILE *)NULL)
  1490.         {
  1491.         sprintf (errbuf, "%s: can't open newfile %s", cmd, newfile);
  1492.         perror (errbuf);
  1493.         exit (2);
  1494.         }
  1495. }
  1496.  
  1497.  
  1498. /*
  1499.  * close both files
  1500.  */
  1501. closefiles ()
  1502. {
  1503.     fclose (oldfp);
  1504.     fclose (newfp);
  1505. }
  1506.  
  1507.  
  1508. /*
  1509.  * dump contents of symbol table
  1510.  * For now, only the old line number and the line of text.
  1511.  */
  1512. dumpsym ()
  1513. {
  1514.     register int i;
  1515.  
  1516.     printf ("Symbol Table Contents:\n");
  1517.     printf ("------ ----- --------\n");
  1518.     printf ("old_line_num: <line of text>\n");
  1519.     for (i = 0; i < BIGPRIME; ++i)
  1520.         if (symtbl[i].olinenum != 0)
  1521.             printf ("%d: %s\n", symtbl[i].olinenum, symtbl[i].stashline);
  1522. }
  1523.  
  1524.  
  1525. /*
  1526.  * get number of old lines which match new lines.
  1527.  *
  1528.  * return the number of lines number n in the old file such that
  1529.  * startline <= n < endline which are linked to lines in the new
  1530.  * file, and are strictly monotonically increasing in the new file (doesn't
  1531.  * have to be monotonically increasing by one, but it can't be the same).
  1532.  * Once the monotonical increase stops, we stop counting.
  1533.  * 'startline' is definitely matched to some line in new file.
  1534.  */
  1535.  
  1536. gomatch (startline, endline)
  1537.     int    startline,
  1538.         endline;
  1539.  
  1540. {
  1541.     register int    count,    /* lines counted in old file        */
  1542.             newi,    /* current new line number last matched    */
  1543.             oldi;    /* current old line number        */
  1544.  
  1545.  
  1546.     /* stop counting lines if reach endline or find non-monitonical
  1547.      * increase in the new file.  newi set to zero is virtual line begin.
  1548.      */
  1549.     for (oldi = startline, count = 0, newi = 0;
  1550.         oldi < endline && oldi <= lastold+1; ++oldi)
  1551.         if (oa[oldi].flag != L_LINENUM)        /* old line doesn't match any new line */
  1552.             continue;            /* so skip old line */
  1553.         else if (oa[oldi].lineloc > newi)    /* monotonical? */
  1554.             {
  1555.             newi = oa[oldi].lineloc;    /* yes, save new line number */
  1556.             ++count;
  1557.             }
  1558.         else
  1559.             break;                /* no, stop counting */
  1560.  
  1561.     return count;
  1562. }
  1563.  
  1564.  
  1565. /*
  1566.  * same idea as gomatch, except count lines in new file which match lines in
  1567.  * old file and old file lines are strictly monotonically increasing
  1568.  */
  1569. gnmatch (startline, endline)
  1570.     int    startline,
  1571.         endline;
  1572.  
  1573. {
  1574.     register int    count,
  1575.             oldi,
  1576.             newi;
  1577.  
  1578.  
  1579.     /* stop counting lines if reach endline or find non-monitonical
  1580.      * increase in the old file.  oldi set to zero is virtual line begin.
  1581.      */
  1582.     for (newi = startline, count = 0, oldi = 0;
  1583.         newi < endline && newi <= lastnew+1; ++newi)
  1584.         if (na[newi].flag != L_LINENUM)        /* new line doesn't match any new line */
  1585.             continue;            /* so skip new line */
  1586.         else if (na[newi].lineloc > oldi)    /* monotonical? */
  1587.             {
  1588.             oldi = na[newi].lineloc;    /* yes, save old line number */
  1589.             ++count;            /* bump count */
  1590.             }
  1591.         else
  1592.             break;                /* no, stop counting */
  1593.  
  1594.     return count;
  1595. }
  1596. SHAR_EOF
  1597. if test 34748 -ne "`wc -c < 'hdiff.c'`"
  1598. then
  1599.     echo shar: error transmitting "'hdiff.c'" '(should have been 34748 characters)'
  1600. fi
  1601. fi
  1602. echo shar: extracting "'remwhite.c'" '(5649 characters)'
  1603. if test -f 'remwhite.c'
  1604. then
  1605.     echo shar: will not over-write existing file "'remwhite.c'"
  1606. else
  1607. cat << \SHAR_EOF > 'remwhite.c'
  1608. /*
  1609.  * f=remwhite.c
  1610.  * author - dennis bednar  8 30 84
  1611.  *
  1612.  * library and standalone routine to remove excess white space from a string.
  1613.  * If there are multiple white spaces together they are transformed into
  1614.  * one blank character.  New lines (if any) in the string are not touched.
  1615.  * A string can consist of more than one line (ie multiple '\n' newline
  1616.  * separators in the string), but usually a string will
  1617.  * consist of one line followed by newline, and then terminated.
  1618.  *
  1619.  * White space at the beginning of each line in the string is reduced to
  1620.  * one blank, if rem1stwhite=0;
  1621.  * White space at the beginning of each line in the string is reduced to
  1622.  * no-blanks, if rem1stwhite=1;
  1623.  * White space for between 2nd, 3rd, etc. non-whites is in each line is
  1624.  * reduced to one blank.
  1625.  * White space at the end of the line in the string is REMOVED.
  1626.  */
  1627.  
  1628. #include <stdio.h>
  1629. #include "stripnl.h"
  1630.  
  1631. char *fgets ();
  1632.  
  1633. /* max strlen (number of chars) returned by remwhite */
  1634. #define MAXSTRING 1024    
  1635.  
  1636. /* max line length that main can handle */
  1637. #define    LINESIZE    1024        /* user sees max line length */
  1638. #define _LINESIZE    LINESIZE+2    /* declare buffer size room for "\n\0" at end*/
  1639.  
  1640.  
  1641. /* last char at the end is for the NULL terminator */
  1642. /* this is the output buffer returned by remwhite() */
  1643. static    char    obuffer [MAXSTRING+1];
  1644.  
  1645. char *
  1646. remwhite (inbuf, rem1stwhite)
  1647.     char *inbuf;
  1648.     char    rem1stwhite;    /* 0 = leave leading white space if any */
  1649.                 /* 1 = remove leading white space if any */
  1650.  
  1651. {
  1652.     register    char    *src,    /* current pointer into input buf */
  1653.                 *dst,    /* current pointer into output buf */
  1654.                 *end;    /* first char AFTER end of output buffer */
  1655.     int        inwhite;    /* true iff in middle of white space */
  1656.  
  1657.  
  1658.     inwhite = 0;
  1659.  
  1660.     /* initialize the src and dest ptrs */
  1661.     src = inbuf;
  1662.     dst = obuffer;
  1663.  
  1664. nextline:
  1665.  
  1666.     /* skip over leading white space in this 'line' in input buffer */
  1667.     /* DONT treat newlines as white space, otherwise, if there were
  1668.      * multiple lines in the input string, then we would remove them,
  1669.      * and we don't want to.
  1670.      * src is positioned at the beginning of a line within inbuf.
  1671.      */
  1672.     if (rem1stwhite)
  1673.         for (; *src; ++src)
  1674.             if (*src == ' ' || *src == '\t')
  1675.                 continue;
  1676.             else
  1677.                 break;    /* found first non-white input char */
  1678.  
  1679.     /* this logic is implemented to output the blank char AFTER
  1680.      * an inwhite to !inwhite state transition.
  1681.      * The reason is so that white space at the end
  1682.      * of the string will be removed.
  1683.      */
  1684.     for (end = &obuffer[sizeof(obuffer)]; *src; ++src)
  1685.         {
  1686.         if (*src == ' ' || *src == '\t')
  1687.             inwhite = 1;    /* don't output anything, just remember we're seeing white space */
  1688.         else if (inwhite)    /* transition, time to output the old blank */
  1689.             {
  1690.             inwhite = 0;
  1691.             *dst++ = ' ';
  1692.             if (dst >= end)
  1693.                 goto error;
  1694.             *dst++ = *src;
  1695.             if (*src == '\n')    /* found end of a line in the input buffer */
  1696.                 goto nextline;    /* work on beginning of next line */
  1697.             }
  1698.         else
  1699.             *dst++ = *src;
  1700.  
  1701.         /* prevent output buffer overflows */
  1702.         if (dst >= end)
  1703.             {
  1704. error:
  1705.             fprintf (stderr, "remwhite: overran buffer.  More than %d chars.\n", MAXSTRING);
  1706.             exit (5);
  1707.             }
  1708.         }
  1709.  
  1710.  
  1711.     /* terminate the string */
  1712.     *dst = '\0';
  1713.  
  1714.     return obuffer;
  1715. }
  1716.  
  1717. #ifdef STAND
  1718.  
  1719. /*
  1720.  * test out the remwhite function
  1721.  */
  1722.  
  1723. static    char    *cmd;    /* name of this command */
  1724.  
  1725.  
  1726. /*
  1727.  * usage:
  1728. cmd [-a] [file ...]    # -a means remove leading white space in each line
  1729.             # if no file(s) given, use stdin
  1730.  */
  1731.  
  1732.  
  1733.  
  1734. main (argc, argv)
  1735.     int argc;
  1736.     char **argv;
  1737. {
  1738.     register    int i;
  1739.     int    striplead = 0;    /* default is DONT zap leading blanks */
  1740.                 /* ie default is to keep leading white space */
  1741.                 /* 1 would change " 1   2" to "1 2" */
  1742.                 /* 0 would leave  " 1   2" as " 1 2" */
  1743.  
  1744.     cmd = argv [0];
  1745.  
  1746.     /* first process possible options */
  1747.     for (i = 1; i < argc; ++i)
  1748.         if (strcmp(argv[i], "-a") == 0)
  1749.             {
  1750.             striplead = 1;
  1751.             continue;
  1752.             }
  1753.         else
  1754.             break;
  1755.  
  1756.     /* i now is index of first file in arg list, if any */
  1757.  
  1758.     if (i == argc)
  1759.         dofile ("", striplead);    /* read from stdin */
  1760.     else for ( ;i < argc; ++i)    /* read each file */
  1761.         dofile (argv[i], striplead);
  1762.  
  1763.     exit (0);    /* normal */
  1764. }
  1765.  
  1766. /*
  1767.  * process a file
  1768.  */
  1769. dofile (filename, zapflag)
  1770.     char *filename;
  1771.     int    zapflag;    /* 1 = zap leading white space */
  1772. {
  1773.     FILE    *infp,        /* input file    */
  1774.         *fopen ();    /* fopen (3)    */
  1775.  
  1776.     if (*filename == '\0')
  1777.         {
  1778.         filename = "[stdin]";    /* in case we need to print file name */
  1779.         infp = stdin;
  1780.         }
  1781.     else
  1782.         {
  1783.         infp = fopen (filename, "r");
  1784.         if (infp == (FILE *)NULL)
  1785.             {
  1786.             sprintf (obuffer, "%s: can't open %s", cmd, filename);
  1787.             perror (obuffer);
  1788.             exit (2);
  1789.             }
  1790.         }
  1791.  
  1792.     dolines (infp, filename, zapflag);
  1793.  
  1794.  
  1795.     fclose (infp);
  1796. }
  1797.  
  1798.  
  1799. /*
  1800.  * process the lines
  1801.  */
  1802. dolines (infp, filename, zapflag)
  1803.     FILE    *infp;        /* stream pointer to read the input file    */
  1804.     char    *filename;    /* name of file we are reading from (for msg) */
  1805.     int    zapflag;    /* 1 = zap leading white space */
  1806. {
  1807.     char    buffer [_LINESIZE],    /* hold line from stdin here */
  1808.         *cp;        /* get pointer to compressed line */
  1809.     int    stat,        /* status after stripping newline */
  1810.         linenum;    /* current line number we are reading */
  1811.  
  1812.     /* read lines from infp and take out the blanks */
  1813.     /* print them to show the effect */
  1814.     linenum = 0;
  1815.     while (fgets (buffer, sizeof(buffer), infp) != (char *) NULL)
  1816.         {
  1817.         ++linenum;
  1818.  
  1819.         stat = stripnl (buffer, sizeof(buffer) );
  1820.  
  1821.         if (stat == L_SUCCESS)
  1822.             ;        /* okay */
  1823.         else if (stat == L_BADFORM)
  1824.             fprintf (stderr, "%s: Warning, line %d in file %s not terminated by newline.\n", cmd, linenum, filename);
  1825.         else
  1826.             {
  1827.             fprintf (stderr, "%s: Line %d in file %s longer than %d chars\n", cmd, linenum, filename, LINESIZE);
  1828.             exit (4);
  1829.             }
  1830.  
  1831.         cp = remwhite (buffer, zapflag);
  1832.  
  1833.         printf ("%s\n", cp);
  1834.         }
  1835. }
  1836.  
  1837.  
  1838.  
  1839.  
  1840. #endif
  1841. SHAR_EOF
  1842. if test 5649 -ne "`wc -c < 'remwhite.c'`"
  1843. then
  1844.     echo shar: error transmitting "'remwhite.c'" '(should have been 5649 characters)'
  1845. fi
  1846. fi
  1847. echo shar: extracting "'stripnl.c'" '(1745 characters)'
  1848. if test -f 'stripnl.c'
  1849. then
  1850.     echo shar: will not over-write existing file "'stripnl.c'"
  1851. else
  1852. cat << \SHAR_EOF > 'stripnl.c'
  1853. /*
  1854.  * f=stripnl.c
  1855.  * author - dennis bednar 8 31 84
  1856.  *
  1857.  * this routine is designed to work in conjunction with fgets ().
  1858.  * In this case, the L_BUFOVER error should never be returned, but
  1859.  * the check is there anyway!
  1860.  *
  1861.  * strip new lines by converting the newline in the string to a null
  1862.  * returns
  1863.  *    L_BUFOVER = buffer is overfilled.  For example if bufsize = 10, then
  1864.  *        the string len could be at most 9 (so the NULL fits)
  1865.  *    L_TOOLONG = no newline was found (line too long) and buffer was filled.
  1866.  *        For a bufsize of 10, buffer[9] is the last char, and it's
  1867.  *        not the expected newline.
  1868.  *    L_BADFORM = no newline was found and buffer not filled, so bad format
  1869.  *    L_SUCCESS = success
  1870.  */
  1871.  
  1872. #include "stripnl.h"
  1873.  
  1874. stripnl (buffer, bufsize)
  1875.     char    *buffer;
  1876.     int    bufsize;
  1877. {
  1878.     char    *cp;
  1879.     int    len;    /* number of chars in string */
  1880.  
  1881.  
  1882.     /* get string length */
  1883.     len = strlen (buffer);
  1884.  
  1885.     /* make sure it's not already overrun */
  1886.     if (len >= bufsize)
  1887.         return (L_BUFOVER);
  1888.  
  1889.     /* if "" is passed, len is zero, and so 'last char' doesn't exist */
  1890.     if (len <= 0)
  1891.         return (L_BADFORM);
  1892.  
  1893.     /* now the string definitely fits in the buffer */
  1894.  
  1895.     /* get pointer to last char in string */
  1896.     cp = &buffer [len - 1];
  1897.  
  1898.     /* if the last char of the string is a newline, change it to a NULL */
  1899.     if (*cp == '\n')
  1900.         {
  1901.         *cp = '\0';
  1902.         return L_SUCCESS;
  1903.         }
  1904.  
  1905.     /* now the string fits in the buffer, and the last char != '\n' */
  1906.  
  1907.     /* line too long if the string length is the buffer size minus
  1908.      * one for the null.
  1909.      */
  1910.     else if (len >= bufsize-1)
  1911.         return L_TOOLONG;
  1912.  
  1913.     /* badly formatted if the line fits in the buffer, but
  1914.      * contains no newline at the end.
  1915.      * This happens on a file which is corrupted by, say,
  1916.      * a transmission error.
  1917.      */
  1918.     else
  1919.         return L_BADFORM;
  1920. }
  1921. SHAR_EOF
  1922. if test 1745 -ne "`wc -c < 'stripnl.c'`"
  1923. then
  1924.     echo shar: error transmitting "'stripnl.c'" '(should have been 1745 characters)'
  1925. fi
  1926. fi
  1927. echo shar: extracting "'stripnl.h'" '(125 characters)'
  1928. if test -f 'stripnl.h'
  1929. then
  1930.     echo shar: will not over-write existing file "'stripnl.h'"
  1931. else
  1932. cat << \SHAR_EOF > 'stripnl.h'
  1933. /* returned from the function stripnl */
  1934. #define L_BUFOVER -2
  1935. #define L_TOOLONG -1
  1936. #define L_BADFORM  0
  1937. #define L_SUCCESS  1
  1938. SHAR_EOF
  1939. if test 125 -ne "`wc -c < 'stripnl.h'`"
  1940. then
  1941.     echo shar: error transmitting "'stripnl.h'" '(should have been 125 characters)'
  1942. fi
  1943. fi
  1944. exit 0
  1945. #    End of shell archive
  1946.